package algorithms.leaning.class30;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 先序遍历：第一次打印，第二次不打
 * 中序遍历：第一次不打，第二次打印
 * 后续遍历：第一次不打印，第二次逆序打印左树的右边界，最后逆序打印整棵树的右边界
 *
 * @author guichang
 * @date 2021/7/3
 */

@SuppressWarnings("all")
public class Code2_二叉树_Morris前中后序遍历 {

    public static void main(String[] args) {
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7);
        MyUtil.printf("先序遍历: {}", morrisPre(treeNode)); // 1245367
        MyUtil.printf("中序遍历: {}", morrisMiddle(treeNode)); // 4251637
        MyUtil.printf("后序遍历: {}", morrisPos(treeNode)); // 4526731
    }

    /**
     * 先序遍历
     * 在morris序的基础上，第二次不打印
     */
    public static List<Integer> morrisPre(TreeNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        TreeNode curr = head;
        while (curr != null) {
            TreeNode mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                // 第一次来到左树右边界
                if (mostRight.right == null) {
                    res.add(curr.val);
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }
                // 第二次来到左树右边界
                else if (mostRight.right == curr) {
                    mostRight.right = null;
                }
            } else {
                res.add(curr.val);
            }
            curr = curr.right;
        }
        return res;
    }

    /**
     * 中序遍历
     * 在morris序的基础上，第一次不打印
     */
    public static List<Integer> morrisMiddle(TreeNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        TreeNode curr = head;
        while (curr != null) {
            TreeNode mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                // 第一次来到左树右边界
                if (mostRight.right == null) {
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }
                // 第二次来到左树右边界
                else if (mostRight.right == curr) {
                    res.add(curr.val);
                    mostRight.right = null;
                }
            } else {
                res.add(curr.val);
            }
            curr = curr.right;
        }
        return res;
    }

    /**
     * 后续遍历
     * 在morris序的基础上，第二次逆序打印左树的右边界，最后逆序打印整棵树的右边界所有节点
     */
    public static List<Integer> morrisPos(TreeNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        TreeNode curr = head;
        while (curr != null) {
            TreeNode mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                // 第一次来到左树右边界
                if (mostRight.right == null) {
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }
                // 第二次来到左树右边界
                else if (mostRight.right == curr) {
                    // 恢复原始结构
                    mostRight.right = null;
                    // 逆序记录左树右边界所有节点
                    recordEdge(curr.left, res);
                }
            } else {

            }
            curr = curr.right;
        }
        // 逆序记录整棵树的右边界所有节点
        recordEdge(head, res);
        return res;
    }

    /**
     * 逆序记录head的右边界所有节点
     */
    private static void recordEdge(TreeNode head, List<Integer> res) {
        // 逆序并返回新头节点
        TreeNode reverseHead = reverseTree(head);
        // 记录逆序链
        for (TreeNode curr = reverseHead; curr != null; curr = curr.right) {
            res.add(curr.val);
        }
        // 恢复原始结构
        reverseTree(head);
    }

    /**
     * 原地逆序链表
     */
    private static TreeNode reverseTree(TreeNode head) {
        TreeNode pre = null, next = head;
        while (next != null) {
            TreeNode temp = next.right;
            next.right = pre;
            pre = next;
            next = temp;
        }
        return pre;
    }

}